#include <vector>
#include <iostream>

using namespace std;

//动态规划(斐波那契数列模型)01：第 N 个泰波那契数（含空间优化）
class Solution1 {
public:
    int tribonacci(int n) 
    {
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        int a=0,b=1,c=1;
        int d;
        int cut=n-2;
        while(cut--)
        {
            d=a+b+c;
            a=b;b=c;c=d;
        }
        return d;    
    }
};


//动态规划(斐波那契数列模型)02：三步问题（含空间优化）
class Solution2 {
public:
    int waysToStep(int n) 
    {
        if(n==1)return 1;
        if(n==2)return 2;
        if(n==3)return 4;
        int cut=n-3;
        int a=1,b=2,c=4;
        long long d;
        while(cut--)
        {
            d=((a+b)%1000000007+c)%1000000007;
            a=b;b=c;c=d;
        }
        return d;
    }
};

//动态规划(斐波那契数列模型)03：使用最小花费爬楼梯(含空间优化)
class Solution3 {
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        int n=cost.size();
        //dp0==0,dp1==0;dp2=min(cost0+dp0,cost1+dp1),dp3=min(cost1+dp1,cost2+dp2);
        //vector<int> dp(n+1);
        int a=0,b=0;int c;
        //dp[0]=0;dp[1]=0;
        // for(int i=2;i<=n;i++)
        // {
        //     dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        // }
        // return dp[n];
        for(int i=2;i<=n;i++)
        {
            c=min(a+cost[i-2],b+cost[i-1]);
            a=b;b=c;
        }
        return c; 
    }
};



//动态规划(斐波那契数列模型)04：解码方法
class Solution4 {
public:
    int numDecodings(string s) 
    {
        if(s[0]=='0')   return 0;
        int n=s.size();  
        vector<int> dp(n+1);
        if(s[0]!='0') dp[0]=1;
        else dp[0]=0;
        if(n==1)    return dp[0];
        if(s[1]!='0') dp[1]+=1;
        int tmp=0;
        tmp=(s[0]-'0')*10+s[1]-'0';
        if(tmp>=10&&tmp<=26)    dp[1]+=1;
        for(int i=2;i<n;i++)
        {
            if(s[i]!='0') dp[i]+=dp[i-1];
            tmp=(s[i-1]-'0')*10+s[i]-'0';
            if(tmp>=10&&tmp<=26)    dp[i]+=dp[i-2];
        }
        return dp[n-1];
    }
};

int main()
{
    return 0;
}
